import java.util.Random;

public class quick {
    //补充快速排序之中的 三路排序
    public static void quicksort(int[] arr){
        quickfun(arr,0,arr.length-1);
    }

    public static void quickfun(int[] arr,int start,int end){
        if (start>=end){
            return;
        }
            int par=partition(arr,start,end);

            quickfun(arr,start,par-1);
            quickfun(arr,par+1,end);

    }

    public static int partition(int[] arr,int left,int right){
        Random random=new Random();
        int rand=random.nextInt(right-left+1)+left;
        swap(arr,left,rand);
        int target =arr[left];
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            if (arr[cur]<target){
                swap(arr,cur,prev);
                prev++;
                cur++;
            }else if (arr[cur]>target){
                swap(arr,cur,right);
                right--;
            }else{
                cur++;
            }
        }
        return prev;
    }

    public static void swap(int[] arr,int a,int b){
        int cur=arr[a];
        arr[a]=arr[b];
        arr[b]=cur;
    }
}
